package cn.com.klun.tjy.other.suanfa;

import java.util.Stack;

/**
 * 汉诺塔游戏
 */
public class HanNuoTaGame {
//    public static void main(String[] args) {
//
//        // 显然用栈结构来存比较好
//        Stack<Integer> as = new Stack();
//        Stack<Integer> bs = new Stack();
//        Stack<Integer> cs = new Stack();
//        as.add(4);
//        as.add(3);
//        as.add(2);
//        as.add(1);
//        System.out.println(as.peek());
//        System.out.println(as.peek());
//        System.out.println(bs.peek());
//        System.out.println(bs.empty());
//    }

    public static void hnt1(int num, Stack<Integer> as,Stack<Integer> bs,Stack<Integer> cs){
        // 赋值
        for (int i = num; i < 0; i--) {
            as.add(i);
        }
        // 初始条件
        bs.add(as.pop());
        cs.add(as.pop());
        cs.add(bs.pop());
        System.out.println("++++++++++打印初始的结果+++++++++++");
        System.out.println("init: "+as);
        System.out.println("from: "+cs);
        System.out.println("to: "  +bs);
        calculate1(2,as,cs,bs);

    }

    /**
     *
     * @param useF
     * @param init
     * @param from
     * @param to
     */
    public static void calculate1(int useF,Stack<Integer> init,Stack<Integer> from,Stack<Integer> to){

        // 跳出循环逻辑
        if((init.empty()&&(from.empty()||to.empty()))){
            System.out.println("******第次结果:最终结果");
            System.out.println("init:"+init);
            System.out.println("from:"+from);
            System.out.println("to:"+to);
            return ;
        }
        // 第一次的判断逻辑
        // 判断 init from to
        Integer a = (null != init.peek()) ? init.peek():0;
        Integer b = (null != from.peek()) ? from.peek():0;
        Integer c = (null != to.peek()) ? to.peek():0;

        // a b c 排序
        if(a >= b && b >= c){ // a>b>c

        }

    }

    // 基数为 3 的方法
    public static void base3(int useF,Stack<Integer> init,Stack<Integer> from,Stack<Integer> to){
        base2(0,init,from,to);
        // 移动 1 2 到 to
        Integer i1 = init.pop();
        to.add(i1);

        Integer f1 = from.pop();
        init.add(f1);

        Integer f2 = from.pop();
        to.add(f2);

        Integer i2 = init.pop();
        to.add(i2);
    }

    // 基数为 2 的方法
    public static void base2(int useF,Stack<Integer> init,Stack<Integer> from,Stack<Integer> to){
        // 从 init 移动 1 2 分别到from 和to
        from.add(init.pop());
        to.add(init.pop());
        to.add(from.pop());
    }



    public static void hnt(int num, Stack<Integer> as,Stack<Integer> bs,Stack<Integer> cs){
        // 赋值
        for (int i = num; i < 0; i--) {
            as.add(i);
        }
        // 此参数记录 每个栈中的最大值
        int maxA = num;
        int maxB = 0;
        int maxC = 0;
        // 此参数记录 每个栈中的个数
        int sizeA = num;
        int sizeB = 0;
        int sizeC = 0;
//        HanNuoTaGame.calculate(maxA,maxB,maxC,sizeA,sizeB,sizeC,as,bs,cs,0,
//                new Stack<Integer>(),new Stack<Integer>(),new Stack<Integer>());

    }
    // 直到 B C  栈有一个为空为一个循环 --记录顺序的数量，找中间栈
    public static int calculate(int maxA,int maxB,int maxC,int sizeA,int sizeB,int sizeC,Stack<Integer> as,Stack<Integer> bs,Stack<Integer> cs,int count,
            Stack<Integer> at,Stack<Integer> bt,Stack<Integer> ct){
        // 退出逻辑
        if((as.empty()&&(bs.empty()||cs.empty()))){
            System.out.println("******第"+count+"次结果:最终结果");
            System.out.println("as:"+as);
            System.out.println("bs:"+bs);
            System.out.println("cs:"+cs);
            return 0;
        }

        // 总数和最大值一样  并且 剩下一个栈的个数为 零
        count ++;

        // 情况一：
        if(maxB == sizeB && sizeC == 0){
            cs.add(as.peek());
            sizeA--;
            sizeC++;
            maxC = as.peek();
            as.pop();
            if(sizeA == 0){
                maxA = 0;
            }

            System.out.println("******第"+count+"次结果");
            System.out.println(as);
            System.out.println(bs);
            System.out.println(cs);
            HanNuoTaGame.calculate(maxA,maxB,maxC,sizeA,sizeB,sizeC,as,bs,cs,count,new Stack<Integer>(),new Stack<Integer>(),new Stack<Integer>());
        }

        // 情况二：
        if(maxB == sizeB){
            // 把b拿出来放到1 再拿一个放到c
            Integer b = bs.pop();
            sizeB--;
            // 如果此时bs为空 放到顶端 == 2 的栈
            if(b == maxB){
                maxB = 0;
                cs.add(b);
                HanNuoTaGame.calculate(maxA,maxB,maxC,sizeA,sizeB,sizeC,as,bs,cs,count,new Stack<Integer>(),new Stack<Integer>(),new Stack<Integer>());
            }
            if(b != maxB){
                Integer b1 = bs.pop();
            }
            as.add(b);
            sizeB--;
            sizeA++;

            cs.add(bs.pop());
            sizeB--;
            sizeC++;
            cs.add(as.pop());
            sizeA--;
            sizeC++;
        }
        return 1;
    }

    public static int hut2(int num,String left,String mid,String rirht){
        if(num < 1){
            return 0;
        }
        return process(num,left,mid,rirht,left,rirht);
    }

    private static int process(int num, String left, String mid, String rirht, String from, String to) {
        if(num == 1){
            if(from.equals(mid) || to.equals(mid)){
                System.out.println("Move 1 from "+ from +"to" + to);
                return 1;
            }else{
                System.out.println("Move 1 from "+ from + "to" +mid);
                System.out.println("Move 1 from "+ mid + "to" +to);
                return 2;
            }
        }
        if(from.equals(mid) || to.equals(mid)){
            String another = (from.equals(left)||to.equals(left))?rirht:left;
            int part1 = process(num - 1,left,mid,rirht,from,another);
            int part2 = 1;
            System.out.println("Move"+num+"form"+from+"to"+to);
            int part3 = process(num - 1,left,mid,rirht,another,to);
            return part1 + part2 + part3;
        }else {
            int part1 = process(num - 1,left,mid,rirht,from,to);
            int part2 = 1;
            System.out.println("Move "+num + "from "+from +"to "+mid);
            int part3 = process(num -1,left,mid,rirht,to,from);
            int part4 = 1;
            System.out.println("Move "+num + "from "+mid +"to "+to);
            int part5 = process(num-1,left,mid,rirht,from,to);
            return part1+part2+part3+part4+part5;
        }
    }

    /**
     * 
     * @param n 盘子的数目
     * @param origin 源座
     * @param assist 辅助座
     * @param destination 目的座
     */
    public void hanoi(int n, char origin, char assist, char destination){
        if(n == 1){
            move(origin,destination);
        } else {
            hanoi((n-1),origin,destination,assist);
            move(origin,destination);
            hanoi(n-1,assist,origin,destination);
        }
    }
    private void move(char origin,char destination){
        System.out.println("Direction:"+origin+"--->"+destination);
    }


    public static void hanoiStack(int n, Stack origin, Stack assist, Stack destination,int count){
        count ++;
        if(n == 1){
            moveASstep(origin,destination);
        } else {
            hanoiStack((n-1),origin,destination,assist,count);//n=5 n=4 n=3 n=2
            moveASstep(origin,destination);// n=2 n=3
            hanoiStack(n-1,assist,origin,destination,count);//n=2 n=3 n=4 n=5
        }
    }
    private static void moveASstep(Stack origin,Stack destination){
        destination.add(origin.pop());
    }

    public static void hnt111(int num, Stack<Integer> as,Stack<Integer> bs,Stack<Integer> cs){
        // 赋值
        for (int i = num; i > 0; i--) {
            as.add(i);
        }
        long l = System.currentTimeMillis();
        hanoiStack(num,as,cs,bs,0);
        System.out.println((System.currentTimeMillis()-l)/1000+" 秒");

    }
    public static void main(String[] args) {
        Stack<Integer> as = new Stack<>();
        Stack<Integer> bs = new Stack<>();
        Stack<Integer> cs = new Stack<>();
        hnt111(5,as,bs,cs);
    }
}
